邻接矩阵图Graph——数据结构系列教程(c++版)

#ifndef ARRAYGRAPH_H_INCLUDED
#define ARRAYGRAPH_H_INCLUDED

//************************************************************************************************************************************************************************
//
//      类名：邻接矩阵图(ArrayGraph),全称：Adjacency Matrix Graph
//
//      概述：一个可复用的数组邻接矩阵图，存储结构采用二维数组实现。
//
//      邻接矩阵：分为V和E集合，其中，V是顶点，E是边。因此，用一个一维数组存放图中所有顶点数据；用一个二维数组存放顶点间关系（边或弧）的数据，这个二维数组称为邻接矩阵。
//
//      功能：包含创建图、添加顶点、添加边、连通测试、最短路径、打印邻接矩阵、深度优先遍历（DFS）、广度优先遍历（BFS） 等核心功能。
//
//      说明：
//
//************************************************************************************************************************************************************************

#define MAX_VERTEX 100  // 最大顶点数（可根据需求调整）
#define NO_EDGE 0       //表示无边
#define INF INT_MAX     // 无边/无穷大标记
#define NO_PRE -1       // 路径前驱的无效标记

//========================================================================================================================================================================
//
//                                                              邻接矩阵图结构体(ArrayGraph)
//
//========================================================================================================================================================================
struct ArrayGraph
{
    //------------------------------------------------------------------------------------------------------
    //                                          私有成员                                                ||
    // 注：私有成员只能在该结构体内部访问调用，外部通过该结构体定义(实体化)的变量(对象)不能访问调用）   ||
    //------------------------------------------------------------------------------------------------------
    private:

        //---------------声明私有成员变量---------------

        //---------------声明私有成员函数---------------
        
        int findMinDist(int dist[], bool visited[], int n);//找到未访问的距离最小的顶点  dist 距离数组  visited 访问标记数组  n 顶点数 距离最小的顶点索引，无则返回-1
        void printPath(int pre[], int startIndex, int targetIndex);//打印路径（递归回溯前驱数组）  pre 前驱数组  startIndex 起始顶点索引  targetIndex 目标顶点索引
        int dfsCheckConnect(int startIndex, int targetIndex, bool visited[]);//DFS辅助函数：判断从startIndex能否到达targetIndex visited 访问标记数组 能到达返回1，否则返回0
        void dijkstra(int startIndex, int dist[], int pre[]);//Dijkstra算法：计算起始顶点到所有顶点的最短路径 startIndex 起始顶点索引  dist 输出参数：存储起始顶点到各顶点的最短距离  pre 输出参数：存储各顶点的路径前驱索引
        void dfsHelper(int index, bool visited[]);//DFS辅助函数：index 当前顶点索引 visited 访问标记数组


    //------------------------------------------------------------------------------------------------------
    //                                          公共成员                                                ||
    // 注：公共成员能在该结构体内部访问调用，外部通过该结构体定义(实体化)的变量(对象)也能访问调用）     ||
    //------------------------------------------------------------------------------------------------------
    public:

        //---------------声明公共成员变量---------------

        char vertices[MAX_VERTEX];          // 顶点集合（存储顶点名称，如'A'、'B'）
        int graph[MAX_VERTEX][MAX_VERTEX];  // 邻接矩阵
        int vertexNum;                      // 实际顶点数
        int edgeNum;                        // 实际边数

        //---------------声明公共成员函数---------------

        // 构造函数：外部通过该结构体定义(实例化)变量(对象)时，自动执行该函数(主要用于初始化成员变量的值)
        ArrayGraph() {
            vertexNum = edgeNum = 0;
             // 初始化邻接矩阵为NO_EDGE（无边）
             for (int i = 0; i < MAX_VERTEX; i++) {
                 for (int j = 0; j < MAX_VERTEX; j++) {
                    graph[i][j] = NO_EDGE;
                 }
             }
        }

        int findVertexIndex(char vertex);//查找顶点的索引,未找到返回-1
        int addVertex(char vertex);//添加顶点 vertex 顶点名称（如'A'）
        int addEdge(char v1, char v2, int weight);//添加边（无向图）v1 顶点1 v2 顶点2 weight 边的权值（需>0，NO_EDGE=0表示无边）
        int addDirectedEdge(char v1, char v2, int weight);//添加边（有向图）v1 顶点1 v2 顶点2 weight 边的权值（需>0，NO_EDGE=0表示无边）
        void printAdjacency();//打印邻接矩阵
        int isConnected(char v1, char v2);//判断两个顶点是否连通 v1 顶点1 v2 顶点2 连通返回1，不连通返回0，顶点不存在返回-1
        int getShortestPath(char start, char target);//获取两顶点的最短路径（封装Dijkstra） start 起始顶点  target 目标顶点  最短路径长度（INF表示无路径，-1表示顶点不存在）
        void dfs(char start);//深度优先遍历（DFS） start 起始顶点
        void bfs(char start);//广度优先遍历（BFS）start 起始顶点

        // 析构函数：自动销毁邻接矩阵图，避免内存泄漏
        ~ArrayGraph() {
        }
};

#endif // ARRAYGRAPH_H_INCLUDED
                

ArrayGraph.cpp 程序代码

#include  <stdio.h>
#include  <stdlib.h>
#include  <stdbool.h>
#include "ArrayGraph.h"
//**********************实现私有成员函数**********************

//找到未访问的距离最小的顶点  dist 距离数组  visited 访问标记数组  n 顶点数 距离最小的顶点索引，无则返回-1
int ArrayGraph::findMinDist(int dist[], bool visited[], int n) {
    int min = INF;
    int minIndex = -1;

    for (int i = 0; i < n; i++) {
        if (!visited[i] && dist[i] < min) {
            min = dist[i];
            minIndex = i;
        }
    }
    return minIndex;
}

//打印路径（递归回溯前驱数组）  pre 前驱数组  startIndex 起始顶点索引  targetIndex 目标顶点索引
void ArrayGraph::printPath(int pre[], int startIndex, int targetIndex) {
    if (targetIndex == startIndex) {
        printf("%c", vertices[targetIndex]);
        return;
    }
    if (pre[targetIndex] == NO_PRE) {
        printf("无路径");
        return;
    }
    // 递归打印前驱路径
    printPath( pre, startIndex, pre[targetIndex]);
    printf(" -> %c", vertices[targetIndex]);
}

//DFS辅助函数：判断从startIndex能否到达targetIndex visited 访问标记数组 能到达返回1，否则返回0
int ArrayGraph::dfsCheckConnect(int startIndex, int targetIndex, bool visited[])
{
    // 找到目标顶点，返回连通
    if (startIndex == targetIndex) {
        return 1;
    }

    visited[startIndex] = true;

    // 遍历所有邻接顶点
    for (int j = 0; j < vertexNum; j++) {
        // 有边且未访问
        if (graph[startIndex][j] != NO_EDGE && !visited[j]) {
            // 递归检查邻接顶点是否能到达目标
            if (dfsCheckConnect(j, targetIndex, visited)) {
                return 1;
            }
        }
    }

    // 所有邻接顶点都遍历完仍未找到，返回不连通
    return 0;
}

//Dijkstra算法：计算起始顶点到所有顶点的最短路径 startIndex 起始顶点索引  dist 输出参数：存储起始顶点到各顶点的最短距离  pre 输出参数：存储各顶点的路径前驱索引
void ArrayGraph::dijkstra(int startIndex, int dist[], int pre[]) {
    int n = vertexNum;
    bool sq[MAX_VERTEX] = {false};//初始化sq默认为false，false代表未确定最短路径的结点集合Q，true代表已经确定最短路径的结点集合S

    // 1. 初始化距离和前驱数组
    for (int i = 0; i < n; i++) {
        if (i == startIndex) {
            dist[i] = 0;                // 起始顶点到自身距离为0
            pre[i] = NO_PRE;            // 自身无前驱
        } else if (graph[startIndex][i] != NO_EDGE) {
            dist[i] = graph[startIndex][i];  // 初始化起始顶点的直连边的dist距离为权值
            pre[i] = startIndex;             // 初始化起始顶点的直连边的pre前驱为起始顶点
        } else {
            dist[i] = INF;              // 初始化其它顶点的dist距离为无穷大(INF)
            pre[i] = NO_PRE;            // 初始化其它顶点的pre前驱为无前驱(NO_PRE)
        }
    }
    sq[startIndex] = true;

    // 2. 依次计算每个节点的距离和前驱
    for (int i = 1; i < n; i++) {
        // 从Q中找出一个从起点到该结点代价最小的结点u
        int u = 0;
        int min = INF;
        for (int i = 0; i < n; i++) {
            if (!sq[i] && dist[i] < min) {
                min = dist[i];
                u = i;
            }
        }
        if (u == -1) break; // 所有可达顶点已处理
        sq[u] = true;// 将u从Q中移出，并放入S中

        // 对u的每一个相邻结点v进行松驰操作
        for (int v = 0; v < n; v++) {
            if (!sq[v] && graph[u][v] != NO_EDGE && dist[u] != INF) {
                if (dist[u] + graph[u][v] < dist[v]) {
                    dist[v] = dist[u] + graph[u][v];//更新距离
                    pre[v] = u; // 更新前驱
                }
            }
        }
    }
}

//深度优先遍历（DFS）index 当前顶点索引 visited 访问标记数组
void ArrayGraph::dfsHelper(int index, bool visited[])
{
    // 标记当前顶点为已访问，并打印
    visited[index] = true;
    printf("%c ", vertices[index]);

    // 遍历所有邻接顶点
    for (int j = 0; j < vertexNum; j++) {
        // 存在边且未访问
        if (graph[index][j] > NO_EDGE && !visited[j]) {
            dfsHelper(j, visited);
        }
    }
}


//**********************实现公有成员函数**********************

//查找顶点的索引,未找到返回-1
int ArrayGraph::findVertexIndex(char vertex)
{
    for (int i = 0; i < vertexNum; i++) {
       if (vertices[i] == vertex) {
           return i;
       }
    }
    printf("顶点%c不存在！\n", vertex);
    return -1;
}

  //添加顶点 vertex 顶点名称（如'A'）
int ArrayGraph::addVertex(char vertex)
{
    if (vertexNum >= MAX_VERTEX) {
        printf("顶点数已达上限，无法添加！\n");
        return 0;
    }
    vertices[vertexNum++] = vertex;
    return 1;
}

//添加边（无向图）v1 顶点1 v2 顶点2 weight 边的权值（需>0，NO_EDGE=0表示无边）
int ArrayGraph::addEdge(char v1, char v2, int weight)
{
    int i = findVertexIndex(v1);
    int j = findVertexIndex(v2);

    if (i == -1 || j == -1) {
        return 0;
    }

    // 无向图：双向置weight
    graph[i][j] = weight;
    graph[j][i] = weight;
    edgeNum++;
    return 1;
}

//添加边（有向图）v1 顶点1 v2 顶点2 weight 边的权值（需>0，NO_EDGE=0表示无边）
int ArrayGraph::addDirectedEdge(char v1, char v2, int weight)
{
    int i = findVertexIndex(v1);
    int j = findVertexIndex(v2);

    if (i == -1 || j == -1) {
        return 0;
    }

    // 有向图：单向置weight
    graph[i][j] = weight;
    edgeNum++;
    return 1;
}

//打印邻接矩阵
void ArrayGraph::printAdjacency()
{
    printf("\n===== 带权邻接矩阵 =====\n");
    // 打印顶点名称（表头）
    printf("   "); // 对齐
    for (int i = 0; i < vertexNum; i++) {
        printf("%3c", vertices[i]);
    }
    printf("\n");

    // 打印邻接矩阵内容
    for (int i = 0; i < vertexNum; i++) {
        printf("%3c", vertices[i]);
        for (int j = 0; j < vertexNum; j++) {
            // 无边显示0，有边显示权值
            printf("%3d", graph[i][j]);
        }
        printf("\n");
    }
    printf("========================\n");
}

//判断两个顶点是否连通 v1 顶点1 v2 顶点2 连通返回1，不连通返回0，顶点不存在返回-1
int ArrayGraph::isConnected(char v1, char v2)
{
    // 1. 查找顶点索引
    int i = findVertexIndex(v1);
    int j = findVertexIndex(v2);

    // 顶点不存在
    if (i == -1 || j == -1) {
        return -1;
    }

    // 2. 同一个顶点，直接连通
    if (i == j) {
        return 1;
    }

    // 3. 初始化访问标记数组
    bool visited[MAX_VERTEX] = {false};

    // 4. 通过DFS检查连通性
    return dfsCheckConnect(i, j, visited);
}

 //获取两顶点的最短路径（封装Dijkstra） start 起始顶点  target 目标顶点  最短路径长度（INF表示无路径，-1表示顶点不存在）
int ArrayGraph::getShortestPath(char start, char target) {
    // 1. 检查顶点合法性
    int startIndex = findVertexIndex(start);
    int targetIndex = findVertexIndex(target);
    if (startIndex == -1 || targetIndex == -1) {
        return -1;
    }

    // 2. 同一顶点，路径长度为0
    if (startIndex == targetIndex) {
        printf("\n===== 最短路径（%c → %c）=====\n", start, target);
        printf("路径：%c\n", start);
        printf("最短路径长度：0\n");
        return 0;
    }

    // 3. 初始化距离和前驱数组
    int dist[MAX_VERTEX];
    int pre[MAX_VERTEX];
    dijkstra(startIndex, dist, pre);

    // 4. 输出结果
    printf("\n===== 最短路径（%c → %c）=====\n", start, target);
    if (dist[targetIndex] == INF) {
        printf("路径：无\n");
        printf("最短路径长度：∞（无连通路径）\n");
        return INF;
    } else {
        printf("路径：");
        printPath(pre, startIndex, targetIndex);
        printf("\n最短路径长度：%d\n", dist[targetIndex]);
        return dist[targetIndex];
    }
}

//深度优先遍历（DFS） start 起始顶点
void ArrayGraph::dfs(char start)
{
    int startIndex = findVertexIndex(start);
    if (startIndex == -1) {
        return;
    }

    // 初始化访问标记数组
    bool visited[MAX_VERTEX] = {false};
    printf("\n===== 深度优先遍历（起始：%c）=====\n", start);
    dfsHelper(startIndex, visited);
    printf("\n");
}

//广度优先遍历（BFS）start 起始顶点
void ArrayGraph::bfs(char start)
{
    int startIndex = findVertexIndex(start);
    if (startIndex == -1) {
        return;
    }

    // 初始化访问标记数组和队列
    bool visited[MAX_VERTEX] = {false};
    int queue[MAX_VERTEX]; // 简单队列（数组实现）
    int front = 0, rear = 0; // 队列头尾指针

    printf("\n===== 广度优先遍历（起始：%c）=====\n", start);

    // 起始顶点入队并标记访问
    visited[startIndex] = true;
    queue[rear++] = startIndex;

    // 队列不为空时循环
    while (front < rear) {
        // 出队并打印
        int currIndex = queue[front++];
        printf("%c ", vertices[currIndex]);

        // 遍历所有邻接顶点
        for (int j = 0; j < vertexNum; j++) {
            if (graph[currIndex][j] > NO_EDGE && !visited[j]) {
                visited[j] = true;
                queue[rear++] = j;
            }
        }
    }
    printf("\n");
}

main.cpp 测试代码

#include "ArrayGraph.h"
#include <iostream>
#include <string>

int main() {
    //  A ── B
    //  │    │
    //  C ── D ── E
    printf("\n===== 图 =====\n");
    printf("  A ── B\n");
    printf("  │    │\n");
    printf("  C ── D ── E\n");

    //使用MyLibrary函数库中的ArrayGraph(邻接矩阵图结构体)定义graph变量
    ArrayGraph graph;

    //使用MyLibrary函数库中的LinkedGraph(邻接链表图结构体)定义graph变量
    //LinkedGraph graph;

    // 1. 添加顶点（A、B、C、D、E）
    graph.addVertex('A');
    graph.addVertex('B');
    graph.addVertex('C');
    graph.addVertex('D');
    graph.addVertex('E');

    // 2. 添加边（无向图）
    graph.addEdge('A','B',1);
    graph.addEdge('A','C',1);
    graph.addEdge('B','D',1);
    graph.addEdge('C','D',1);
    graph.addEdge('D','E',1);

    // 2. 添加边（有向图）
    //graph.addDirectedEdge('A','B',5);
    //graph.addDirectedEdge('A','C',3);
    //graph.addDirectedEdge('B','D',2);
    //graph.addDirectedEdge('C','D',4);
    //graph.addDirectedEdge('D','E',1);

    // 3. 打印邻接矩阵
    graph.printAdjacency();

    // 4. 测试连通性函数
    printf("\n===== 顶点连通性测试 =====\n");
    char v1, v2;

    // 测试1：A和B（连通）
    v1 = 'A'; v2 = 'E';
    int res1 = graph.isConnected(v1, v2);
    if (res1 == 1) {
        printf("顶点%c和%c：连通\n", v1, v2);
    } else if (res1 == 0) {
        printf("顶点%c和%c：不连通\n", v1, v2);
    } else {
        printf("顶点%c或%c不存在\n", v1, v2);
    }

    // 5. 测试最短路径（A -> E）
    graph.getShortestPath('A', 'E'); // A→C→D→E，长度3+4+1=8

    // 6. 深度优先遍历（起始：A）
    graph.dfs( 'A');

    // 7 广度优先遍历（起始：A）
    graph.bfs('A');

return 0;
}

输出结果

  A ── B
  │    │
  C ── D ── E

  ===== 带权邻接矩阵 =====
      A   B   C   D   E
  A   0   5   3   0   0
  B   5   0   0   2   0
  C   3   0   0   4   0
  D   0   2   4   0   1
  E   0   0   0   1   0

  ===== 顶点连通性测试 =====
  顶点A和E：连通

  ===== 最短路径（A -> E） =====
  路径：A -> B -> D -> E
  最短路径长度：3

  ===== 深度优先遍历（起始：A）=====
  A B D C E

  ===== 广度优先遍历（起始：A）=====
  A B C D E

===== 图内存已全部释放 =====

六、总结

本文详细解析了邻接矩阵图（ArrayGraph）的原理与代码实现，核心要点：

• 邻接矩阵通过「顶点数组+邻接矩阵数组」存储图，适合稠密图；
• 核心功能封装为类，区分私有/公共成员，符合面向对象设计；
• 实现了DFS/BFS遍历、Dijkstra最短路径、连通性判断等核心算法；
• 完善的内存管理（构造/析构函数）避免内存泄漏。

该实现可直接复用，也可根据需求扩展（如支持负权边的Bellman-Ford算法、拓扑排序等），是学习图结构和算法的优质实践案例。